package com.qf.pojo.day04;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * 走阶梯，有n级阶梯，
 * 一次可以走一级、两级或者三级，请编写一个函数计算走完该阶梯一共有多少种方法。
 *
 *   一级台阶： 1种
 *   二级台阶： 2种走法
 *       1 1
 *       2
 *   三级台阶： 4种
 *      1 1 1
 *      1 2
 *      2 1
 *      3
 *   四级台阶： 7种
 *     1 1 1 1
 *     1 1 2
 *     1 2 1
 *     1 3
 *     ----
 *     2 1 1
 *     2 2
 *     ----
 *     3 1
 *   五级台阶： 13种
 *   六级台阶： 24种
 *   七级台阶： 44种
 *   八级台阶： 81种
 *   ....
 *   n级台阶： 多少种走法   n:规模
 * @author lixu
 */
public class Test {


    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        System.out.println("N级阶梯走法:" + f2(50));// n：无穷大
        //  N级阶梯走法:23837527729
        System.out.println("耗时:" + (System.currentTimeMillis()-startTime) + "ms");
    }


    //缓存  Key:1~50  Value:对应走法的数量
    private static Map cacheMap = new HashMap<Long,Long>();

    //private RedisTemplate redisTemplate;

    // 本地缓存     最快
    // 分布式缓存   连接redis get set close


    /**
     * 走阶梯，有n级阶梯，  O(3^n)
     *
     * 返回值long:走法    参数是规模
     */
    private static long f(long n){//n级阶梯  规模
        //1: n =1 一级台阶
        if(n == 1){
            return 1;
        }
        //2: n =2 二级台阶
        if(n == 2){
            return 2;
        }
        //3: n =3 三级台阶
        if(n == 3){
            return 4;
        }
        //4:从第四级台阶开始
        // 以当前台阶为准 前三级台阶之和    当前台阶是7 = 4台 + 5台 +6台
        //4:先查询缓存中是否有数据
        Long value = (Long) cacheMap.get(n);
        if(value != null){
            //4.1 有
            return value;
        }else{
            //4.2 没有  查询 f(n-1) + f(n-2) + f(n-3)
            //保存到缓存一份
            cacheMap.put(n,f(n-1) + f(n-2) + f(n-3));
        }
        return (Long)(cacheMap.get(n));
    }


    /**
     *
     *   阶梯  走法
     *    1     1
     *    2     2
     *    3     4
     *    4     7
     *    5     13
     *    6     24
     *    7     44
     *
     *    a=1
     *    b=2
     *    c=4
     *    d=a+b+c    4
     *
     *    a=b;
     *    b=c;
     *    c=d;
     *
     *    d=a+b+c    5
     *
     *
     *
     */
    private static long f2(long n){//n级阶梯  规模
        //1: n =1 一级台阶
        if(n == 1){
            return 1;
        }
        //2: n =2 二级台阶
        if(n == 2){
            return 2;
        }
        //3: n =3 三级台阶
        if(n == 3){
            return 4;
        }
        long a=1,b=2,c=4;//3
        long d = 0;//1
        for (int i = 4; i <= n; i++) {
            d=a+b+c;
            a=b;//2
            b=c;//3
            c=d;//4
        }
        return d;
    }






}
